#include "stdio.h"
#include "string.h" 
int judge(int j,int l,char *p)
{   int i,k;
	i=j+l-1;
	if(l==2)
	{   if(*p==*(p+1)) return(1);
	    if(*p!=*(p+1)) return(0);
	}
	if(l>2)
	{   for(k=j;k<=j+l/2-1;k++)
			if(*(p+k)!=*(p+l+j-k-1)) break;
	    if(k>j+l/2-1) return(1);if(k<=j+l/2-1) return(0);
	}
}
int d(int i,char *p)
{   int j,t,z=1000,b[1000]={0};
	if(b[i]>0) return(b[i]);
	if(i==0) return(1);
	if(i==1)
	{   if(*p==*(p+1)) return(1);
		if(*p!=*(p+1)) return(2);
	}
	else if(i>=2)
	{   if(judge(0,i+1,p)==1) z=1;
		else
		{   for(j=i-1;j>=0;j--)
			{   if(j==i-1) t=d(j,p)+1;
				if(j<i-1&&j>=0)
				{   
					if(judge(j+1,i-j,p+j+1)==0) t=d(j,p)+(i-j); 
                    if(judge(j+1,i-j,p+j+1)==1) t=d(j,p)+1;
				}
			    if(t<z) z=t;  b[i]=z;             
			}
		} return(z);
	}
}
main()
{   char a[1000]={'\0'},x[10];
	int T,i,j,l,z;
	scanf("%d",&T);
	gets(x);
	for(i=0;i<T;i++)
	{
		memset(a,0,sizeof(a));
		gets(a);
		l=strlen(a);
		z=d(l-1,a);
		printf("%d\n",z);
	}
}
